package 中等.模拟;

import java.util.Arrays;

/**
 * 用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子
 * 的顶部和底部都是开着的。
 * 箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球
 * 导向左侧或者右侧。
 * 将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
 * 将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。
 * 在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。
 * 如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任
 * 意一侧边上，就会卡住。
 * 返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i
 * 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/where-will-the-ball-fall
 */
public class 球会落何处_1706 {

    public static void main(String[] args) {

        int[][] grid = {{1, 1, 1, -1, -1}, {1, 1, 1, -1, -1}, {-1, -1, -1, 1, 1}, {1, 1, 1, 1, -1}, {-1, -1, -1, -1, -1}};
        System.out.println(Arrays.toString(findBall(grid)));

    }

    /**
     * 1 代表 \ ，那么如果右边也是 1 ，[row+1,column+1] ，是球的下一个位置
     * -1 代表 / ，那么如果左边也是 -1 ，[row+1,column-1] ，是球的下一个位置
     * 其余情况均不能从底部出去
     * 注意:
     * 下一个位置列 column 必须在 [0,columns-1] 的范围内
     * 当 row > rows-1 行时，从球从箱子里面出去
     *
     * @param grid
     * @return
     */
    public static int[] findBall(int[][] grid) {
        int rows = grid.length, columns = grid[0].length;
        int[] ans = new int[columns];
        for (int i = 0; i < ans.length; i++) {
            int row = 0, column = i;
            boolean pass = true;
            while (row < rows) {
                if (grid[row][column] == 1 && column + 1 < columns &&
                        grid[row][column + 1] == 1) {
                    row++;
                    column++;
                } else if (grid[row][column] == -1 && column - 1 >= 0 &&
                        grid[row][column - 1] == -1) {
                    row++;
                    column--;
                } else {
                    pass = false;
                    break;
                }
            }
            if (pass) {
                ans[i] = column;
            } else {
                ans[i] = -1;
            }
        }
        return ans;
    }

}
